#ifndef MKAHYPAR_HYPERGRAPH_PRUNER_H
#define MKAHYPAR_HYPERGRAPH_PRUNER_H
#include "mkahypar/utils/typedef.h"
#include "mkahypar/partition/coarsening/coarsening_memento.h"
#include "mkahypar/datastructure/fast_reset_flag_array.h"
#include "mkahypar/partition/metrics.h"
#include "mkahypar/partition/refinement/policies/hop_penalty_policy.h"
namespace mkahypar{
  class HypergraphPruner{
  private:
    struct Fingerprint {
      HyperedgeID id;
      size_t hash;
    };
    struct ParallelHE {
      const HyperedgeID representative_id;
      const HyperedgeID removed_id;
    };
    static constexpr HyperedgeID kInvalidID = std::numeric_limits<HyperedgeID>::max();
  public:
    explicit HypergraphPruner(const HypernodeID max_num_nodes):
    _contained_hypernodes(max_num_nodes){}

    HypergraphPruner(const HypergraphPruner&) = delete;
    HypergraphPruner& operator= (const HypergraphPruner&) = delete;
    HypergraphPruner(HypergraphPruner&&) = delete;
    HypergraphPruner& operator= (HypergraphPruner&&) = delete;
    ~HypergraphPruner() = default;

    //删除单点边
    HyperedgeWeight removeSingleNodeHyperedges(Hypergraph& hg,
                                               CoarseningMemento& memento) {
      memento.one_pin_hes_begin = _removed_single_node_hyperedges.size();
      auto begin_it = hg.incidentEdges(memento.contraction_memento.u).first;
      auto end_it = hg.incidentEdges(memento.contraction_memento.u).second;
      HyperedgeWeight removed_he_weight = 0;
      for (auto he_it = begin_it; he_it != end_it; ++he_it) {
        if (hg.hyperedge(*he_it).size() == 1) {
          _removed_single_node_hyperedges.push_back(*he_it);
          removed_he_weight += hg.edgeWeight(*he_it);
          ++memento.one_pin_hes_size;

//          LOG<<"remove single edge:"<<*he_it;
          hg.removeEdge(*he_it);
          --he_it;
          --end_it;
        }
      }
      return removed_he_weight;
    }
    //删除平行边
    HyperedgeID removeParallelHyperedges(Hypergraph& hypergraph,
                                         CoarseningMemento& memento) {
      memento.parallel_hes_begin = _removed_parallel_hyperedges.size();

      createFingerprints(hypergraph, memento.contraction_memento.u);
      std::sort(_fingerprints.begin(), _fingerprints.end(),
                [](const Fingerprint& a, const Fingerprint& b) { return a.hash < b.hash; });

      size_t i = 0;
      HyperedgeWeight removed_parallel_hes = 0;
      bool filled_probe_bitset = false;
      while (i < _fingerprints.size()) {
        size_t j = i + 1;
        if (_fingerprints[i].id != kInvalidID) {
          while (j < _fingerprints.size() && _fingerprints[i].hash == _fingerprints[j].hash) {
            // If we are here, then we have a hash collision for _fingerprints[i].id and
            // _fingerprints[j].id.
            //平行边检测
            if (_fingerprints[j].id != kInvalidID &&
                hypergraph.edgeSize(_fingerprints[i].id) == hypergraph.edgeSize(_fingerprints[j].id) &&
                hypergraph.hyperedge(_fingerprints[i].id).source() == hypergraph.hyperedge(_fingerprints[j].id).source()) {
              if (!filled_probe_bitset) {
                fillProbeBitset(hypergraph, _fingerprints[i].id);
                filled_probe_bitset = true;
              }
              if (isParallelHyperedge(hypergraph, _fingerprints[j].id)) {
                removed_parallel_hes += 1;
                removeParallelHyperedge(hypergraph, _fingerprints[i].id, _fingerprints[j].id);
                _fingerprints[j].id = kInvalidID;//标记已经被删除
                ++memento.parallel_hes_size;
              }
            }
            ++j;
          }
        }
        // We need pairwise comparisons for all HEs with same hash.
        filled_probe_bitset = false;
        ++i;
      }
      return removed_parallel_hes;
    }
    //删除两条平行边
    void removeParallelHyperedge(Hypergraph& hypergraph,
                                 const HyperedgeID representative,
                                 const HyperedgeID to_remove) {
      hypergraph.setEdgeWeight(representative,
                               hypergraph.edgeWeight(representative)
                               + hypergraph.edgeWeight(to_remove));
      hypergraph.removeEdge(to_remove,representative);
      _removed_parallel_hyperedges.emplace_back(ParallelHE { representative, to_remove });
    }

    void fillProbeBitset(Hypergraph& hypergraph, const HyperedgeID he) {
      _contained_hypernodes.reset();
      for (const HypernodeID& pin : hypergraph.pins(he))
        _contained_hypernodes.set(pin, true);

    }
    bool isParallelHyperedge(Hypergraph& hypergraph, const HyperedgeID he) const {
      bool is_parallel = true;
      for (const HypernodeID& pin : hypergraph.pins(he)) {
        if (!_contained_hypernodes[pin]) {
          is_parallel = false;
          break;
        }
      }
      return is_parallel;
    }

    //创建指纹
    void createFingerprints(Hypergraph& hypergraph, const HypernodeID u) {
      _fingerprints.clear();
      for (const HyperedgeID& he : hypergraph.incidentEdges(u)) {
        _fingerprints.emplace_back(Fingerprint {he, hypergraph.hyperedge(he).hash });
      }
    }

    //恢复单点边
    void restoreSingleNodeHyperedges(Hypergraph& hypergraph,
                                     const CoarseningMemento& memento) {
      for (int i = memento.one_pin_hes_begin + memento.one_pin_hes_size - 1;
           i >= memento.one_pin_hes_begin; --i) {
//        LOG<<"restore single edge:"<<_removed_single_node_hyperedges[i];

        hypergraph.restoreEdge(_removed_single_node_hyperedges[i]);
        _removed_single_node_hyperedges.pop_back();
      }
    }
    //恢复平行边
    void restoreParallelHyperedges(Hypergraph& hypergraph,
                                   const CoarseningMemento& memento) {
      for (int i = memento.parallel_hes_begin + memento.parallel_hes_size - 1;
           i >= memento.parallel_hes_begin; --i) {
        hypergraph.restoreEdge(_removed_parallel_hyperedges[i].removed_id,
                               _removed_parallel_hyperedges[i].representative_id);
        hypergraph.setEdgeWeight(_removed_parallel_hyperedges[i].representative_id,
                                 hypergraph.edgeWeight(_removed_parallel_hyperedges[i].representative_id) -
                                 hypergraph.edgeWeight(_removed_parallel_hyperedges[i].removed_id));
        _removed_parallel_hyperedges.pop_back();
      }
    }
    //恢复平行边,基于真实route count的会改变目标函数值
    void restoreParallelHyperedges(Hypergraph& hypergraph,
                                   const CoarseningMemento& memento,Metrics& best,TargetGraph& topo) {
      for (int i = memento.parallel_hes_begin + memento.parallel_hes_size - 1;
           i >= memento.parallel_hes_begin; --i) {
//        LOG<<"restore parral edge:"<<_removed_parallel_hyperedges[i].representative_id<<_removed_parallel_hyperedges[i].removed_id;
        hypergraph.restoreEdge<NormalHopPenaltyPolicy>(_removed_parallel_hyperedges[i].removed_id,
                               _removed_parallel_hyperedges[i].representative_id,best,topo);
        hypergraph.setEdgeWeight(_removed_parallel_hyperedges[i].representative_id,
                                 hypergraph.edgeWeight(_removed_parallel_hyperedges[i].representative_id) -
                                 hypergraph.edgeWeight(_removed_parallel_hyperedges[i].removed_id));
        _removed_parallel_hyperedges.pop_back();
      }
    }



    std::vector<HyperedgeID> _removed_single_node_hyperedges;
    std::vector<ParallelHE> _removed_parallel_hyperedges;
    std::vector<Fingerprint> _fingerprints;
    ds::FastResetFlagArray<uint64_t> _contained_hypernodes;

  };

}
#endif //MKAHYPAR_HYPERGRAPH_PRUNER_H
